package main

import "fmt"

func bubbleSort(nums []int) {
	l := len(nums)
	for i := 0; i < l-1; i++ {
		var swap = false
		for j := 0; j < l-1-i; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
				swap = true
			}
		}
		if !swap {
			return
		}
	}
}

/*
*
先建堆
再排序
*/
func heapSort(nums []int) {
	buildHeap(nums)
	n := len(nums)
	for i := n - 1; i >= 0; i-- {
		swap(nums, 0, i)
		heapify(nums, i, 0)
	}
}

func heapify(nums []int, n int, i int) {
	max := i
	c1 := i*2 + 1
	c2 := i*2 + 2
	if c1 < n && nums[c1] > nums[max] {
		max = c1
	}

	if c2 < n && nums[c2] > nums[max] {
		max = c2
	}

	if max != i {
		swap(nums, max, i)
		heapify(nums, n, max)
	}
}

func swap(nums []int, a, b int) {
	nums[a], nums[b] = nums[b], nums[a]
}

func buildHeap(nums []int) {
	n := len(nums)
	for i := (n - 1 - 1) / 2; i >= 0; i-- {
		heapify(nums, n, i)
	}
}

///*
//*
//先拆分，再合并
//*/
//func mergeSort(nums []int) []int {
//	if len(nums) <= 1 {
//		return nums
//	}
//
//	mid := len(nums) / 2
//	left := mergeSort(nums[:mid])
//	right := mergeSort(nums[mid:])
//
//	return merge(left, right)
//}
//
//func merge(nums1, nums2 []int) []int {
//	i, j := 0, 0
//	o := []int{}
//	for i < len(nums1) && j < len(nums2) {
//		if nums1[i] < nums2[j] {
//			o = append(o, nums1[i])
//			i++
//		} else {
//			o = append(o, nums2[j])
//			j++
//		}
//	}
//
//	o = append(o, nums1[i:]...)
//	o = append(o, nums2[j:]...)
//	return o
//}

func mergeSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}

	mid := len(nums) / 2
	left := mergeSort(nums[:mid])
	right := mergeSort(nums[mid:])
	return merge(left, right)
}

func merge(nums1, nums2 []int) []int {
	i, j := 0, 0
	var o []int
	for i < len(nums1) && j < len(nums2) {
		if nums1[i] < nums2[j] {
			o = append(o, nums1[i])
			i++
		} else {
			o = append(o, nums2[j])
			j++
		}
	}

	o = append(o, nums1[i:]...)
	o = append(o, nums2[j:]...)
	return o
}

//func quickSort(nums []int, lo, hi int) {
//	if lo >= hi {
//		return
//	}
//	p := partition(nums, lo, hi)
//	quickSort(nums, lo, p-1)
//	quickSort(nums, p, hi)
//}
//
//func partition(nums []int, lo, hi int) int {
//	i := lo - 1
//	for j := lo; j < hi; j++ {
//		if nums[j] > nums[hi] {
//			i++
//			nums[j], nums[i] = nums[i], nums[j]
//		}
//	}
//	nums[hi], nums[i+1] = nums[i+1], nums[hi]
//	return i + 1
//}

func quickSort(nums []int, lo, hi int) {
	if lo >= hi { //不断二分下去，hi越来越小
		return
	}

	p := partition(nums, lo, hi)
	quickSort(nums, lo, p-1)
	quickSort(nums, p, hi)

}

func partition(nums []int, lo, hi int) int {
	i := lo - 1
	for j := lo; j < hi; j++ {
		if nums[j] > nums[hi] {
			i++
			nums[j], nums[i] = nums[i], nums[j]
		}
	}
	nums[i+1], nums[hi] = nums[hi], nums[i+1]
	return i + 1
}

func main() {
	nums := []int{5, 3, 7, 1, 8, 4}
	quickSort(nums, 0, len(nums)-1)
	fmt.Println(nums)
}
